Chihik's Blog

An Ac a day, keeps the doctor away!

CF900D Unusual Sequences

发布于 2021-02-01 | 分类于 组合数学 、 莫比乌斯反演 | 4分钟 | 602字数 | 浏览量：

建议先做 CF439E。

∑n=1y∑i1=1y∑i2=1y...∑in=1y[∑ai=y][gcd⁡ai=x]\sum_{n=1}^y\sum_{i_1=1}^y\sum_{i_2=1}^y...\sum_{i_n=1}^y [\sum{a_i}=y][\gcd{a_i}=x]

∑n=1y∑i1=1yx∑i2=1yx...∑in=1yx[∑ai=yx][gcd⁡ai=1]\sum_{n=1}^y\sum_{i_1=1}^{\frac{y}{x}}\sum_{i_2=1}^\frac{y}{x}...\sum_{i_n=1}^\frac{y}{x} [\sum{a_i}=\frac{y}{x}][\gcd{a_i}=1]

∑n=1y∑d∣yxμ(d)∑i1=1yxd∑i2=1yxd...∑if=1yxd[∑ai=yxd]\sum_{n=1}^y\sum_{d|\frac{y}{x}} \mu(d) \sum_{i_1=1}^{\frac{y}{xd}}\sum_{i_2=1}^{\frac{y}{xd} }...\sum_{i_f=1}^{\frac{y}{xd}} [\sum{a_i}=\frac{y}{xd}]

后面枚举 ii 的过程可以看作将 yxd\frac{y}{xd} 个相同的球放进 nn 个不同的盒子，且不能有空盒的方案数，利用插板法可得： (yxd−1n−1)\binom{\frac{y}{xd}-1}{n-1}

那么原式即为：

∑n=1y∑d∣yxμ(d)(yxd−1n−1)\sum_{n=1}^y\sum_{d|\frac{y}{x}} \mu(d) \binom{\frac{y}{xd} - 1 }{n-1}

∑d∣yxμ(d)∑n=1y(yxd−1n−1)\sum_{d|\frac{y}{x}}\mu(d) \sum_{n=1}^y\binom{\frac{y}{xd} - 1 }{n-1}

∑d∣yxμ(d)∑n=1yxd(yxd−1n−1)\sum_{d|\frac{y}{x}}\mu(d) \sum_{n=1}^{\frac{y}{xd}}\binom{\frac{y}{xd} - 1 }{n-1}

∑d∣yxμ(d)∑n=1yxd(yxd−1n−1)\sum_{d|\frac{y}{x}}\mu(d) \sum_{n=1}^{\frac{y}{xd}}\binom{\frac{y}{xd} - 1 }{n-1}

∑d∣yxμ(d)2yxd−1\sum_{d|\frac{y}{x}}\mu(d) 2^{\frac{y}{xd}-1} 

#include <cstdio>

const int MAXN = 1e5 , Mod = 1e9 + 7;

int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = 1ll * x * x % Mod ) if( po & 1 ) p = 1ll * p * x % Mod; return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }

int mu( int n ) {
	int Ans = 1;
	for( int i = 2 ; i * i <= n ; i ++ )
		if( n % i == 0 ) {
			int p = 0; for( ; n % i == 0 ; n /= i ) p ++;
			if( p > 1 ) return 0;
			Ans *= -1;
		}
	if( n > 1 ) Ans *= -1;
	return Ans;
}

int x , y;
int main( ) {
	scanf("%d %d",&x,&y);
	if( y % x != 0 || y < x ) return printf("0\n") & 0;

	int Ans = 0;
	for( int d = 1 ; d * d <= y / x ; d ++ )
		if( y / x % d == 0 ) {
			Ans = ( Ans + mu( d ) * Quick_pow( 2 , y / x / d - 1 ) % Mod ) % Mod;
			if( d * d != y / x )
				Ans = ( Ans + mu( y / x / d ) * Quick_pow( 2 , d - 1 ) % Mod ) % Mod;
		}
	printf("%d\n", ( Ans + Mod ) % Mod );
	return 0;
}
# 组合数学 # 莫比乌斯反演
CF547C Mike and Foam 上一篇
CF439E Devu and Birthday Celebration 下一篇
0%